#include <bits/stdc++.h>
using namespace std;

// int main() {
//     vector<void*> LRU_vec(10);

// }
// 数组实现LRU
template<typename T>
class LRU {
    public:
        LRU(int size = 0) {
            _lru_vec = vector<T>(size);
        };
        ~LRU() {

        };

        void add(T& data) {
            for (int i = 0; i < _used_size; ++i) {
                if (data == _lru_vec[i]) {
                    // cache hit
                    for (int j = i; j > 0; --j) {
                        _lru_vec[j] = _lru_vec[j-1];
                    }
                    _lru_vec[0]  = data;
                    return;
                }
            }
            // cache miss
            if (_used_size < _lru_vec.size()) {
                
            } else {
                _used_size--;
            }
            for (int j = _used_size; j > 0; --j) {
                    _lru_vec[j] = _lru_vec[j-1];
                }
            _lru_vec[0] = data;
            _used_size++;
        }

        int size() {
            return _used_size;
        }
    private:
        vector<T> _lru_vec;
        int _used_size = 0;
};

// 链表实现LRU
template<typename T> 
class LRU_list {
    public:
        LRU_list(int size = 0):_max_size(size)
            {}
        ~LRU_list() {}
        void add(T& data) {
            for (auto it = _lru_list.begin(); it!= _lru_list.end(); ++it) {
                if (data == (*it)) {
                    _lru_list.erase(it);
                    _lru_list.push_front(data);
                    return;
                }
            }
            if (_cur_size < _max_size) {
                _lru_list.push_front(data);
                _cur_size++;
            } else {
                _lru_list.pop_back();
                _lru_list.push_front(data);
                _cur_size++;
            }
        }
        void print() {
            for (auto it:_lru_list) {
                cout << it << " ";
            }
            cout << endl;
        }
    private:
        int _max_size;
        int _cur_size = 0;
        list<T> _lru_list;
};

int main() {
    vector<int> test = {1, 3, 1, 4, 5, 1, 1, 2, 4};
    LRU_list<int> lru(4);
    for (auto num: test) {
        lru.add(num);
        lru.print();
    }
}